package LeetCode;

public class SearchInsertPos
{
  public int searchInsert(int[] A, int target)
  {
    // Start typing your Java solution below
    // DO NOT write main() function
    int result = bs(A, target);
    if (result == -1) return 0;
    if (A[result] == target) return result;
    return result + 1;
  }

  public int bs(int[] a, int x)
  {
    int start = 0, end = a.length - 1, mid = (a.length - 1) / 2;
    int ret = -1;

    while (start <= end) {
      mid = (start + end) / 2;
      if (a[mid] > x) {
        end = mid - 1;
      }
      else {
        start = mid + 1;
        ret = mid;
      }
    }

    return ret;
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub

  }

}
